package com.uyong.study.maze;

import java.awt.Point;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * DFS算法寻找路径
 * 
 * @author gonggy
 */
public class DFSSearchStrategy implements SearchPathStrategy {

	@Override
	public Point[] search(int[][] array) {
		Stack<Point> stack = new Stack<>();// 用于寻找路径时的栈
		stack.push(new Point(1, 1));
		array[1][1] = BlockStatus.VISTID;
		int size = array.length;
		while (!stack.isEmpty() && (stack.peek().x != size - 2 || stack.peek().y != size - 2)) {
			if (array[stack.peek().x][stack.peek().y + 1] == BlockStatus.OPEN) { // right
				stack.push(new Point(stack.peek().x, stack.peek().y + 1));
				array[stack.peek().x][stack.peek().y] = BlockStatus.VISTID;
			} else if (array[stack.peek().x + 1][stack.peek().y] == BlockStatus.OPEN) { // down
				stack.push(new Point(stack.peek().x + 1, stack.peek().y));
				array[stack.peek().x][stack.peek().y] = BlockStatus.VISTID;
			} else if (array[stack.peek().x - 1][stack.peek().y] == BlockStatus.OPEN) { // up
				stack.push(new Point(stack.peek().x - 1, stack.peek().y));
				array[stack.peek().x][stack.peek().y] = BlockStatus.VISTID;
			} else if (array[stack.peek().x][stack.peek().y - 1] == BlockStatus.OPEN) { // left
				stack.push(new Point(stack.peek().x, stack.peek().y - 1));
				array[stack.peek().x][stack.peek().y] = BlockStatus.VISTID;
			} else {
				array[stack.peek().x][stack.peek().y] = BlockStatus.COMMON;
				stack.pop();
			}
		}
		return getPathLocation(stack).toArray(new Point[0]);
	}

	// 得到路径坐标
	private List<Point> getPathLocation(Stack<Point> sw) {
		LinkedList<Point> p = new LinkedList<>();// 用于存储路径坐标
		while (!sw.isEmpty()) {
			p.addFirst(new Point(sw.peek().x, sw.peek().y));
			sw.pop();
		}
		return p;
	}
}
